

class LinkedStack:
    """
    LIFO stack implementation using a singly linked list for storage
    """

    class _Node:
        """Singly linked node"""
        __slots__ = '_element', '_next'

        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        """Create an empty singly linked stack"""
        self._next: LinkedStack._Node = None
        self._size = 0

    def __str__(self):
        data = []
        walk_node: LinkedStack._Node = self._next
        while walk_node:
            data.append(walk_node._element)
            walk_node = walk_node._next
        return str(data)

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def push(self, value):
        """Add element to the top of the stack"""
        self._next = self._Node(value, self._next)
        self._size += 1

    def top(self):
        """Return the element at the top of the stack"""
        if self.is_empty():
            raise Exception("Stack is empty")
        return self._next._element

    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        value = self._next._element
        self._next = self._next._next
        self._size -= 1
        return value

    def recursive_reverse(self):
        """
        对不带head的单向链表进行逆序
        """
        def __recursive_reverse(head):
            """
            递归实现单向链表逆序操作
            [1, 2, 3, 4] -> [4, 3, 2, 1]
            """
            if head is None or head._next is None:
                return head
            else:
                # 先反转头结点1 后面的节点1->[2 3 4], 递归反转
                new_head = __recursive_reverse(head._next)
                # 将头结点 放到 链表的尾部
                head._next._next = head
                head._next = None
                return new_head
        if self._next is None:
            return self._next
        self._next = __recursive_reverse(self._next)

    def insertion_reverse(self):
        """
        插入法实现逆序
        从链表的第二个节点开始把遍历到的节点插入到头结点的后面
        1 -> 2 -> 3 ->4
        变成2 -> 1 -> 3 ->4，
        再变成3 -> 2 -> 1 -> 4，
        最后4 -> 3 -> 2 -> 1
        """
        prev = None
        walk  = self._next
        while walk is not None:
            next = walk._next
            walk._next = prev
            prev = walk
            walk = next
        self._next = prev
